1. Field of Invention
This invention relates to linkers and, more particularly, to methods and apparatus for providing dynamic and extensible attributes to object files to make the linking process more flexible.
2. Background of the Invention
Modern software is often developed in a modular fashion, using a combination of custom code written for the particular application and generic code that may be used in many applications. Reusable modules are often packaged in libraries and distributed either in source code or object code format. In the source code, software in one module calls components of another module through symbolic references. For example, an application that performs digital signal processing might call a standard Fast Fourier Transform component of a standard module by calling the component by its function name in the source code, e.g., fft( ).
Compiling and Linking
The process of building a final executable application from individual source code files involves several steps, which are usually performed by a set of programmer tools designed for that purpose. Source code files are typically compiled into object files individually, and then combined by a linker to make a single executable binary. The linker performs at least two separate functions. First, the linker must satisfy references that are undefined within a source code module. In the example above, if the source code to the digital signal processing application calls the fft( ) function, the linker must satisfy that symbolic reference by locating a suitable definition of the function in one of the other modules involved in the linking process. In effect, the linker must match the definition of a symbol to all the uses of that symbol elsewhere in the source code. If a symbol is referenced but is not defined anywhere else in the source code, the linker may signal the user with a warning or error message that it was unable to resolve the symbolic reference.
Second, the linker must resolve symbols to memory addresses. After identifying and resolving all of the required components, the linker must arrange those components within the memory space of the application. Each component is given a memory address. As in the example above, the fft( ) function could be given a memory address of 0x1000. Once all of the components are given memory addresses, the linker converts all of the symbolic references within the application into those memory addresses so the application can be executed by a CPU. In the fft( ) example, each symbolic reference to the function fft( ) could be resolved to reference the memory address 0x1000. FIG. 1 illustrates the process of compiling source code, resolving symbolic references, and linking into an executable image file.
Static and Dynamic Linking
Linking can be static or dynamic. A static linker bundles a component together with the components it references, as well as all components referenced by those components, until all of the necessary modules are contained in a single executable. Static linking allows the developer to distribute a single binary without needing to ensure that other dependencies already exist on a target system. Static linking, in some cases, also results in performance gains. On the other hand, static linking may require more memory and disk space than dynamic linking. Dynamic linking means that the data in a library is not copied into a new executable or library at compile time, but remains in a separate file on disk. In this case, the linker only records what libraries are required when the application is compiled and the tasks of satisfying undefined references and resolving symbols to memory addresses is done when the application is executed (i.e., at runtime). Dynamic linking allows the same library to be used by multiple applications, thereby conserving disk space and potentially memory.
Libraries
A library is a collection of functions or procedures used to develop applications. It is common to organize several related functions together into a single library. For example, the fft( ) Fast Fourier Transform routine discussed above may be grouped with several related functions used in digital signal processing. A programmer developing a digital signal processing application can then include the digital signal processing library in his application and reference functions defined in that library without having to redefine those functions for each new application.
During the linking process, the linker searches through all included libraries in order to resolve any references made by the application to symbols that are not defined in the application itself. The linker may also perform the task of searching through a list of directories to find the required libraries. As discussed above, the linking may be either static or dynamic.
Libraries provide a means for organizing code and data. Routines with similar characteristics are often collected into a single library. When an application includes multiple libraries, the linker will search these libraries in some defined order to determine which library contains the definition necessary to resolve a particular reference. Linkers are commonly provided with a search order, either by default or by the programmer, for performing this search. Once the linker finds a definition for an unresolved symbol, it usually stops searching at that point, and thus the first library in the search order that provides a particular definition is used, even if other libraries later in the search order also contain definitions for that same symbol. Since the same symbol may have different definitions in several libraries, the programmer can control which symbol definitions will be used to a limited extent by altering the specified search order.
Libraries may be divided along several different conceptual categories. For example, libraries for the Analog Devices Blackfin processor are divided among functional, performance, and target-processor boundaries. As an example of a functional division, there are libraries that handle input/output functions and other libraries that provide floating-point computation emulation functions. As an example of a performance division, there are libraries that implement floating-point computation according to different levels of precision and speed. As an example of a target-processor division, different libraries may contain definitions for the same symbols, with the functions in each library optimized to work on a particular processor or architecture. There are also alternative versions of libraries that provide the same symbol definitions with and without debugging information for the programmer.
Sections
When source code is compiled into object files, the contents of each object file are typically divided into several sections (or “segments”). Each section has its own symbolic name. The symbolic name for each section provides information to the linker on how the contents of that section must be processed. Usually, the compiler and the linker share a common lexicon for interpreting different section symbolic names. For example, the compiler may separate code and data into different sections, and the linker allocates different memory addresses to the contents of those sections based on the content type defined by the symbolic name for each section. This convention allows a linker to satisfy constraints imposed by the physical requirements of target hardware. For example, some processors require executable instructions (code) and data to be stored separately, and prohibit them from coexisting within the same area of memory. Once the compiler identifies sections of the object file as code and data, the linker can then allocate each section to the proper area of memory to function properly according to the target architecture's requirements.
Not all sections of an object file are necessarily mapped into the final executable file. For example, compiler-generated debugging information may be placed into sections that are not included in the final executable image. The programmer may configure the linker to include or exclude such debugging sections at link time.
Memory Areas and “Fall-Through”
A computer processor typically has some memory on-chip with the processor and other memory off-chip that is reached through a system bus. The on-chip memory is generally faster but more expensive memory, while the off-chip memory is cheaper, slower, and can be much larger in size. These memory storage areas can be divided further. For example, it is common to have two or more levels of on-chip memory. Some models of Analog Devices, Inc.'s Blackfin processors have a memory hierarchy as depicted in FIG. 2, where L1 and L2 memory are physically located on the chip with the CPU, while L3 memory is external to the CPU. Ideally, code and data that are most often used by the CPU would be stored in the fastest L1 memory, closest to the CPU. Code and data used less often would be stored in L2 memory, and code and data used the least for a given application would be stored in L3 memory for optimal performance and resource usage. By locating code and data at various memory locations, a linker can assist in optimizing performance and resource use according to these parameters.
Embedded processors like Analog Devices Blackfin processors may have several different memory areas, each with different characteristics. It is common for memory areas to be have different properties such as whether they can be written to (or only read), how much storage they contain, or how quickly they can be accessed. For example, the following table illustrates a potential layout of memory for an Analog Devices Blackfin processor:
Memory AreaContent typeAccess KindSizeSpeedInternal CodeCodeRead-onlySmallFastInternal DataDataRead-writeSmallFastLocal RAMCode/dataRead-writeMediumMediumExternal RAMCode/dataRead-writeVery largeSlowExternal ROMCode/dataRead-onlyLargeVery slow
In order to build a functional application, the linker must observe any constraints on memory usage in locating sections. In the table above, for example, the linker must insure that the “content type” and “access kind” limitations are followed when locating sections of object files. Thus, object file sections marked as code must be placed only in memory areas that allow code and not in memory areas that are data-only. Similarly, data that needs to be written by the application can only be placed in a “read-write” area of memory, and not a “read-only” area.
In deciding where in memory to place code and data, linkers typically apply a “fall-through” approach. The linker first allocates sections to the fastest memory, and as that memory is filled up, it “falls through” to slower memory, allocating sections to the slowest memory last. This allocation must be done consistently with the other constraints discussed above. Accordingly, the linker might map sections to memory as shown in the following table:
SectionMaps to Section of MemoryProgram(1) Internal Code(2) Local RAM(3) External RAM(4) External ROMdata1(1) Internal Data(2) Local RAM(2) External RAMconstdata(1) Internal Data(2) Local RAM(3) External RAM(4) External ROM
As this table illustrates, when allocating object code in the “program” section, the linker will first attempt to place the code in the “internal code” memory area, since it is the fastest memory area and allows code. If the linker is unable to fit the “program” section in “internal code” memory, it will successively attempt to place the code in local RAM, external RAM, and external ROM until it has been successfully allocated to a particular area of memory. The same approach would be used for the other sections.
If the programmer allows the linker to place sections of object code in the default areas of memory, the performance of the resulting application may not be optimal. For example, code that is executed frequently might be placed in slower memory while code that is executed less frequently might be placed in faster memory. As another example, code that needs to be accessible to all cores of a multi-core CPU might be placed in memory that can only be accessed by one core. For these reasons, programmers often manually specify areas of memory other than the default area for placing sections of object files by placing explicit mappings within a linker configuration.